home *** CD-ROM | disk | FTP | other *** search
/ GameStar 2004 April / Gamestar_61_2004-04_dvdb.iso / DVDStar / Editace / hltp.exe / {app} / Source Code / Zoners Half-Life Tools / hlbsp / outside.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  2002-11-15  |  15.2 KB  |  544 lines
  1. #include "bsp5.h"
  2.  
  3. //  PointInLeaf
  4. //  PlaceOccupant
  5. //  MarkLeakTrail
  6. //  RecursiveFillOutside
  7. //  ClearOutFaces_r
  8. //  isClassnameAllowableOutside
  9. //  FreeAllowableOutsideList
  10. //  LoadAllowableOutsideList
  11. //  FillOutside
  12.  
  13. static int      outleafs;
  14. static int      valid;
  15. static int      c_falsenodes;
  16. static int      c_free_faces;
  17. static int      c_keep_faces;
  18.  
  19. // =====================================================================================
  20. //  PointInLeaf
  21. // =====================================================================================
  22. static node_t*  PointInLeaf(node_t* node, const vec3_t point)
  23. {
  24.     vec_t           d;
  25.  
  26.     if (node->contents)
  27.     {
  28.         //Log("PointInLeaf::node->contents == %i\n", node->contents);
  29.         return node;
  30.     }
  31.  
  32.     d = DotProduct(g_dplanes[node->planenum].normal, point) - g_dplanes[node->planenum].dist;
  33.  
  34.     if (d > 0)
  35.         return PointInLeaf(node->children[0], point);
  36.  
  37.     return PointInLeaf(node->children[1], point);
  38. }
  39.  
  40. // =====================================================================================
  41. //  PlaceOccupant
  42. // =====================================================================================
  43. static bool     PlaceOccupant(const int num, const vec3_t point, node_t* headnode)
  44. {
  45.     node_t*         n;
  46.  
  47.     n = PointInLeaf(headnode, point);
  48.     if (n->contents == CONTENTS_SOLID)
  49.     {
  50.         return false;
  51.     }
  52.     //Log("PlaceOccupant::n->contents == %i\n", n->contents);
  53.  
  54.     n->occupied = num;
  55.     return true;
  56. }
  57.  
  58. // =====================================================================================
  59. //  MarkLeakTrail
  60. // =====================================================================================
  61. static portal_t* prevleaknode;
  62. static FILE*    pointfile;
  63. static FILE*    linefile;
  64.  
  65. static void     MarkLeakTrail(portal_t* n2)
  66. {
  67.     int             i;
  68.     vec3_t          p1, p2, dir;
  69.     float           len;
  70.     portal_t*       n1;
  71.  
  72.     n1 = prevleaknode;
  73.     prevleaknode = n2;
  74.  
  75.     if (!n1)
  76.     {
  77.         return;
  78.     }
  79.  
  80.     n2->winding->getCenter(p1);
  81.     n1->winding->getCenter(p2);
  82.  
  83.     // Linefile
  84.     fprintf(linefile, "%f %f %f - %f %f %f\n", p1[0], p1[1], p1[2], p2[0], p2[1], p2[2]);
  85.  
  86.     // Pointfile
  87.     fprintf(pointfile, "%f %f %f\n", p1[0], p1[1], p1[2]);
  88.  
  89.     VectorSubtract(p2, p1, dir);
  90.     len = VectorLength(dir);
  91.     VectorNormalize(dir);
  92.  
  93.     while (len > 2)
  94.     {
  95.         fprintf(pointfile, "%f %f %f\n", p1[0], p1[1], p1[2]);
  96.         for (i = 0; i < 3; i++)
  97.             p1[i] += dir[i] * 2;
  98.         len -= 2;
  99.     }
  100. }
  101.  
  102. // =====================================================================================
  103. //  RecursiveFillOutside
  104. //      Returns true if an occupied leaf is reached
  105. //      If fill is false, just check, don't fill 
  106. // =====================================================================================
  107. static int      hit_occupied;
  108. static int      backdraw;
  109. static bool     RecursiveFillOutside(node_t* l, const bool fill)
  110. {
  111.     portal_t*       p;
  112.     int             s;
  113.  
  114.     if ((l->contents == CONTENTS_SOLID) || (l->contents == CONTENTS_SKY) 
  115. #ifdef ZHLT_DETAIL
  116.         || (l->contents == CONTENTS_DETAIL)
  117. #endif
  118.         )
  119.     {
  120.         /*if (l->contents != CONTENTS_SOLID)
  121.             Log("RecursiveFillOutside::l->contents == %i \n", l->contents);*/
  122.  
  123.         return false;
  124.     }
  125.  
  126.     if (l->valid == valid)
  127.     {
  128.         return false;
  129.     }
  130.  
  131.     if (l->occupied)
  132.     {
  133.         hit_occupied = l->occupied;
  134.         backdraw = 1000;
  135.         return true;
  136.     }
  137.  
  138.     l->valid = valid;
  139.  
  140.     // fill it and it's neighbors
  141.     if (fill)
  142.     {
  143.         l->contents = CONTENTS_SOLID;
  144.         l->planenum = -1;
  145.     }
  146.     outleafs++;
  147.  
  148.     for (p = l->portals; p;)
  149.     {
  150.         s = (p->nodes[0] == l);
  151.  
  152.         if (RecursiveFillOutside(p->nodes[s], fill))
  153.         {                                                  // leaked, so stop filling
  154.             if (backdraw-- > 0)
  155.             {
  156.                 MarkLeakTrail(p);
  157.             }
  158.             return true;
  159.         }
  160.         p = p->next[!s];
  161.     }
  162.  
  163.     return false;
  164. }
  165.  
  166. // =====================================================================================
  167. //  ClearOutFaces_r
  168. //      Removes unused nodes
  169. // =====================================================================================
  170. static node_t*  ClearOutFaces_r(node_t* node)
  171. {
  172.     face_t*         f;
  173.     face_t*         fnext;
  174.     face_t**        fp;
  175.     portal_t*       p;
  176.  
  177.     // mark the node and all it's faces, so they
  178.     // can be removed if no children use them
  179.  
  180.     node->valid = 0;                                       // will be set if any children touch it
  181.     for (f = node->faces; f; f = f->next)
  182.     {
  183.         f->outputnumber = -1;
  184.     }
  185.  
  186.     // go down the children
  187.     if (node->planenum != -1)
  188.     {
  189.         //
  190.         // decision node
  191.         //
  192.         node->children[0] = ClearOutFaces_r(node->children[0]);
  193.         node->children[1] = ClearOutFaces_r(node->children[1]);
  194.  
  195.         // free any faces not in open child leafs
  196.         f = node->faces;
  197.         node->faces = NULL;
  198.  
  199.         for (; f; f = fnext)
  200.         {
  201.             fnext = f->next;
  202.             if (f->outputnumber == -1)
  203.             {                                              // never referenced, so free it
  204.                 c_free_faces++;
  205.                 FreeFace(f);
  206.             }
  207.             else
  208.             {
  209.                 c_keep_faces++;
  210.                 f->next = node->faces;
  211.                 node->faces = f;
  212.             }
  213.         }
  214.  
  215.         if (!node->valid)
  216.         {
  217.             // this node does not touch any interior leafs
  218.  
  219.             // if both children are solid, just make this node solid
  220.             if (node->children[0]->contents == CONTENTS_SOLID && node->children[1]->contents == CONTENTS_SOLID)
  221.             {
  222.                 node->contents = CONTENTS_SOLID;
  223.                 node->planenum = -1;
  224.                 return node;
  225.             }
  226.  
  227.             // if one child is solid, shortcut down the other side
  228.             if (node->children[0]->contents == CONTENTS_SOLID)
  229.             {
  230.                 return node->children[1];
  231.             }
  232.             if (node->children[1]->contents == CONTENTS_SOLID)
  233.             {
  234.                 return node->children[0];
  235.             }
  236.  
  237.             c_falsenodes++;
  238.         }
  239.         return node;
  240.     }
  241.  
  242.     //
  243.     // leaf node
  244.     //
  245.     if (node->contents != CONTENTS_SOLID)
  246.     {
  247.         // this node is still inside
  248.  
  249.         // mark all the nodes used as portals
  250.         for (p = node->portals; p;)
  251.         {
  252.             if (p->onnode)
  253.             {
  254.                 p->onnode->valid = 1;
  255.             }
  256.             if (p->nodes[0] == node)                       // only write out from first leaf
  257.             {
  258.                 p = p->next[0];
  259.             }
  260.             else
  261.             {
  262.                 p = p->next[1];
  263.             }
  264.         }
  265.  
  266.         // mark all of the faces to be drawn
  267.         for (fp = node->markfaces; *fp; fp++)
  268.         {
  269.             (*fp)->outputnumber = 0;
  270.         }
  271.  
  272.         return node;
  273.     }
  274.  
  275.     // this was a filled in node, so free the markfaces
  276.     if (node->planenum != -1)
  277.     {
  278.         free(node->markfaces);
  279.     }
  280.  
  281.     return node;
  282. }
  283.  
  284. // =====================================================================================
  285. //  isClassnameAllowableOutside
  286. // =====================================================================================
  287. #define  MAX_ALLOWABLE_OUTSIDE_GROWTH_SIZE 64
  288.  
  289. unsigned        g_nAllowableOutside = 0;
  290. unsigned        g_maxAllowableOutside = 0;
  291. char**          g_strAllowableOutsideList;
  292.  
  293. bool            isClassnameAllowableOutside(const char* const classname)
  294. {
  295.     if (g_strAllowableOutsideList)
  296.     {
  297.         unsigned        x;
  298.         char**          list = g_strAllowableOutsideList;
  299.  
  300.         for (x = 0; x < g_nAllowableOutside; x++, list++)
  301.         {
  302.             if (list)
  303.             {
  304.                 if (!strcasecmp(classname, *list))
  305.                 {
  306.                     return true;
  307.                 }
  308.             }
  309.         }
  310.     }
  311.  
  312.     return false;
  313. }
  314.  
  315. // =====================================================================================
  316. //  FreeAllowableOutsideList
  317. // =====================================================================================
  318. void            FreeAllowableOutsideList()
  319. {
  320.     if (g_strAllowableOutsideList)
  321.     {
  322.         free(g_strAllowableOutsideList);
  323.         g_strAllowableOutsideList = NULL;
  324.     }
  325. }
  326.  
  327. // =====================================================================================
  328. //  LoadAllowableOutsideList
  329. // =====================================================================================
  330. void            LoadAllowableOutsideList(const char* const filename)
  331. {
  332.     char*           fname;
  333.     int             i, x, y;
  334.     char*           pData;
  335.     char*           pszData;
  336.  
  337.     if (!filename)
  338.     {
  339.         return;
  340.     }
  341.     else
  342.     {
  343.         unsigned        len = strlen(filename) + 5;
  344.  
  345.         fname = (char*)Alloc(len);
  346.         safe_snprintf(fname, len, "%s", filename);
  347.     }
  348.  
  349.     if (q_exists(fname))
  350.     {
  351.         if ((i = LoadFile(fname, &pData)))
  352.         {
  353.             Log("Reading allowable void entities from file '%s'\n", fname);
  354.             g_nAllowableOutside = 0;
  355.             for (pszData = pData, y = 0, x = 0; x < i; x++)
  356.             {
  357.                 if ((pData[x] == '\n') || (pData[x] == '\r'))
  358.                 {
  359.                     pData[x] = 0;
  360.                     if (strlen(pszData))
  361.                     {
  362.                         if (g_nAllowableOutside == g_maxAllowableOutside)
  363.                         {
  364.                             g_maxAllowableOutside += MAX_ALLOWABLE_OUTSIDE_GROWTH_SIZE;
  365.                             g_strAllowableOutsideList =
  366.  
  367.                                 (char**)realloc(g_strAllowableOutsideList, sizeof(char*) * g_maxAllowableOutside);
  368.                         }
  369.  
  370.                         g_strAllowableOutsideList[y++] = pszData;
  371.                         g_nAllowableOutside++;
  372.  
  373.                         Verbose("Adding entity '%s' to the allowable void list\n", pszData);
  374.                     }
  375.                     pszData = pData + x + 1;
  376.                 }
  377.             }
  378.         }
  379.     }
  380. }
  381.  
  382. // =====================================================================================
  383. //  FillOutside
  384. // =====================================================================================
  385. node_t*         FillOutside(node_t* node, const bool leakfile, const unsigned hullnum)
  386. {
  387.     int             s;
  388.     int             i;
  389.     bool            inside;
  390.     bool            ret;
  391.     vec3_t          origin;
  392.     const char*     cl;
  393.  
  394.     Verbose("----- FillOutside ----\n");
  395.  
  396.     if (g_nofill)
  397.     {
  398.         Log("skipped\n");
  399.         return node;
  400.     }
  401.  
  402.     //
  403.     // place markers for all entities so
  404.     // we know if we leak inside
  405.     //
  406.     inside = false;
  407.     for (i = 1; i < g_numentities; i++)
  408.     {
  409.         GetVectorForKey(&g_entities[i], "origin", origin);
  410.         cl = ValueForKey(&g_entities[i], "classname");
  411.         if (!isClassnameAllowableOutside(cl))
  412.         {
  413.             if (!VectorCompare(origin, vec3_origin))
  414.             {
  415.                 origin[2] += 1;                            // so objects on floor are ok
  416.  
  417.                 // nudge playerstart around if needed so clipping hulls allways
  418.                 // have a vlaid point
  419.                 if (!strcmp(cl, "info_player_start"))
  420.                 {
  421.                     int             x, y;
  422.  
  423.                     for (x = -16; x <= 16; x += 16)
  424.                     {
  425.                         for (y = -16; y <= 16; y += 16)
  426.                         {
  427.                             origin[0] += x;
  428.                             origin[1] += y;
  429.                             if (PlaceOccupant(i, origin, node))
  430.                             {
  431.                                 inside = true;
  432.                                 goto gotit;
  433.                             }
  434.                             origin[0] -= x;
  435.                             origin[1] -= y;
  436.                         }
  437.                     }
  438.                   gotit:;
  439.                 }
  440.                 else
  441.                 {
  442.                     if (PlaceOccupant(i, origin, node))
  443.                         inside = true;
  444.                 }
  445.             }
  446.         }
  447.     }
  448.  
  449.     if (!inside)
  450.     {
  451.         Warning("No entities exist in hull %i, no filling performed for this hull", hullnum);
  452.         return node;
  453.     }
  454.  
  455.     s = !(g_outside_node.portals->nodes[1] == &g_outside_node);
  456.  
  457.     // first check to see if an occupied leaf is hit
  458.     outleafs = 0;
  459.     valid++;
  460.  
  461.     prevleaknode = NULL;
  462.  
  463.     if (leakfile)
  464.     {
  465.         pointfile = fopen(g_pointfilename, "w");
  466.         if (!pointfile)
  467.         {
  468.             Error("Couldn't open pointfile %s\n", g_pointfilename);
  469.         }
  470.  
  471.         linefile = fopen(g_linefilename, "w");
  472.         if (!linefile)
  473.         {
  474.             Error("Couldn't open linefile %s\n", g_linefilename);
  475.         }
  476.     }
  477.  
  478.     ret = RecursiveFillOutside(g_outside_node.portals->nodes[s], false);
  479.  
  480.     if (leakfile)
  481.     {
  482.         fclose(pointfile);
  483.         fclose(linefile);
  484.     }
  485.  
  486.     if (ret)
  487.     {
  488.         GetVectorForKey(&g_entities[hit_occupied], "origin", origin);
  489.  
  490.  
  491.         {
  492.             Warning("=== LEAK in hull %i ===\nEntity %s @ (%4.0f,%4.0f,%4.0f)",
  493.                  hullnum, ValueForKey(&g_entities[hit_occupied], "classname"), origin[0], origin[1], origin[2]);
  494.             PrintOnce(
  495.                 "\n  A LEAK is a hole in the map, where the inside of it is exposed to the\n"
  496.                 "(unwanted) outside region.  The entity listed in the error is just a helpful\n"
  497.                 "indication of where the beginning of the leak pointfile starts, so the\n"
  498.                 "beginning of the line can be quickly found and traced to until reaching the\n"
  499.                 "outside. Unless this entity is accidentally on the outside of the map, it\n"
  500.                 "probably should not be deleted.  Some complex rotating objects entities need\n"
  501.                 "their origins outside the map.  To deal with these, just enclose the origin\n"
  502.                 "brush with a solid world brush\n");
  503.         }
  504.  
  505.         if (!g_bLeaked)
  506.         {
  507.             // First leak spits this out
  508.             Log("Leak pointfile generated\n\n");
  509.         }
  510.  
  511.         if (g_bLeakOnly)
  512.         {
  513.             Error("Stopped by leak.");
  514.         }
  515.  
  516.         g_bLeaked = true;
  517.             
  518.         return node;
  519.     }
  520.  
  521.     // now go back and fill things in
  522.     valid++;
  523.     RecursiveFillOutside(g_outside_node.portals->nodes[s], true);
  524.  
  525.     // remove faces and nodes from filled in leafs  
  526.     c_falsenodes = 0;
  527.     c_free_faces = 0;
  528.     c_keep_faces = 0;
  529.     node = ClearOutFaces_r(node);
  530.  
  531.     Verbose("%5i outleafs\n", outleafs);
  532.     Verbose("%5i freed faces\n", c_free_faces);
  533.     Verbose("%5i keep faces\n", c_keep_faces);
  534.     Verbose("%5i falsenodes\n", c_falsenodes);
  535.  
  536.     // save portal file for vis tracing
  537.     if ((hullnum == 0) && leakfile)
  538.     {
  539.         WritePortalfile(node);
  540.     }
  541.  
  542.     return node;
  543. }
  544.